package com.zhouhong.muke_leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName: Algorithm-and-Data-Structure
 * @Description:
 * @Author: zhouhong
 * @Create: 2021-04-02 12:32
 **/
//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重
//复的三元组。
// 注意：答案中不可以包含重复的三元组。

public class LeetCode0015 {
    public List<List<Integer>> threeSum(int[] nums) {
        // 1、先排序
        Arrays.sort(nums);
        List<List<Integer>> result = new LinkedList<>();
        // 2、外层循环每一个元素
        for (int i = 0; i < nums.length; i++) {
            // 因为排好序的，num[i]大于 0，说明它后面任何两个数和它的和都不会等于0（大于零）
            if (nums[i] > 0) {
                break;
            }
            // 如果当前元素与上一个元素相同：跳过（避免重复）
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 让左指针指向当前元素的下一个元素，右指针指向数组的尾部
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int threeSum = nums[i] + nums[left] + nums[right];
                // 如果之和小于 0 ,因为已经排好序，让左指针加一，可以让和增大。
                if (threeSum < 0) {
                    left++;
                } else if (threeSum > 0) {
                    right--;
                } else {
                    // 等于0：声明一个数组，分别将找出的三个元素放进去
                    LinkedList<Integer> res = new LinkedList<>();
                    res.add(nums[i]);
                    res.add(nums[left]);
                    res.add(nums[right]);
                    result.add(res);
                    // 如果左边元素的当前元素与下一个元素相同，直接跳过
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    // 如果右边边元素的当前元素与下一个元素相同，直接跳过
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    // 相等结果返回后，左右指针分别移动，进行下一次
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}